#include<stdio.h>
#include<stdlib.h>
 
struct data{
	int x,y,z;
};
typedef data mang[82]; 

char f[100],g[100];
int a[10][10],b[10];
data d[82];
int	i,j,t;
int lose=0;
 
 
void print_() {
	int i,j;
	for(i=1;i<=9;i++){
		for(j=1;j<=9;j++)
			printf("%3d",a[i][j]);
		printf("\n");
	}
}
 
void swap(int *a, int *b){
	int tmp;
	tmp = *a;
	*a = *b;
	*b= tmp;
}
 
//sap xep bang thuat toan quick sort 
void qs(int l,int h,mang k){
	int i,j,key,tmp;
	if(l >= h) return;
	tmp=(l+h)/2;
	key = k[tmp].z;
	i = l; j = h;
	do {
		while(k[i].z<key) ++i;
		while(k[j].z>key) --j;
		if(i <= j){
			swap(&k[i].z,&k[j].z);
			swap(&k[i].x,&k[j].x);
			swap(&k[i].y,&k[j].y);
			++i;--j;
		}
		if (i>j) break;
	} while(i<=j);
	qs(l,j,k); qs(i,h,k);
}
 
int sums(int x,int y){
	int xa = x, ya = y;
	int i,j,m,n,sum=0;
	for(i=1;i<=9;i++) 
		if(a[x][i]==0) ++sum;
	for(j=1;j<=9;j++)
		if(a[j][y]==0 && j!=x ) ++sum;
		
	//m la chi so hang bat dau cua o vuong lon chua o [x,y]
	if (x % 3 ==0) m = x-2;
	else if(x%3==2) m = x-1;
	else {
		m=x;
		x+=2;//x luc nay la chi so hang ket thuc cua o vuong lon
	}
	//n la chi so cot bat dau cua o vuong lon chua o [x,y]
	if (y % 3 ==0) n = y-2;
	else if(y % 3==2) n = y-1;
	else {
		n=y;
		y+=2;//y luc nay la chi so cot ket thuc cua o vuong lon
	}
	
	//kiem tra trong o vuong lon
	for(i=m;i<=m+2;i++)
		for(j=n;j<=n+2;j++)
			if (a[i][j]==0 && i!=xa && j!=ya) ++sum;
	return sum;//sum luc nay chua tong so o trong co lien quan den vi tri [x,y] (ban dau)
}
 
//dem so o con trong
void count_blank(){
	int i,j;
	t=1;
	for(i=1;i<=9;i++)
		for(j=1;j<=9;j++)
			if (a[i][j]==0) {
				d[t].x = i;
				d[t].y = j;
				d[t].z = sums(i,j);
				//d[t].z = sums(i,j)-3;
				++t;
			}
	qs(1,t-1,d);
		//for(i=1;i<=t;i++)
//			{printf("(%d,%d}:%d\n",d[i].x,d[i].y,d[i].z);} 
 
}
 
void find(int x, int y){
	int xa=x, ya=y;
	int i,j,c,m,n,k=0;
	char z;
	for(i=1;i<=9;i++)
		b[i] = 0;
 	//memset(b,0,10*sizeof(int));
	for(i=1;i<=9;i++) 
		if(a[x][i] != 0) --b[a[x][i]];
	for(j=1;j<=9;j++)
		if(a[j][y] != 0) --b[a[j][y]];
	if (x % 3 ==0) m = x-2;
	else if(x%3==2) m = x-1;
	else {
		m=x;
		x=x+2;
	}
	if (y % 3 ==0) n = y-2;
	else if(y % 3==2) n = y-1;
	else {
		n=y;
		y=y+2;
	}
	for(i=m;i<=x;i++)
		for(j=n;j<=y;j++)
			if (a[i][j] != 0) --b[a[i][j]];	
	printf("Xin nhap vao o (%d,%d) nhung gia tri goi y sau: ",xa,ya);
	
	for(i=1;i<=9;i++){
		if(b[i]>=0) printf("%d ",i); else ++k;
	}
	printf("\n");
	if(k<=-9) {
		printf("THUA MAT ROI");
		lose=1;
		return;
	} else {
		while(1){
			scanf("%d",&c);
			for(i=1;i<=9;i++)
				if(b[i]==0 && c==i) {
					break;
				}
			if(i<=9) break;
			else{
				printf("So nhap vao ko hop le!! vui long nhap lai!\n");
				printf("Xin nhap vao o (%d,%d) nhung gia tri goi y sau: ",xa,ya);
				for(i=1;i<=9;i++)
					if(b[i]>=0) printf("%d ",i);
				printf("\n");
			}
		}
		
		a[xa][ya] = c;
		printf("Xem lai bang sudoku? (c/k)");
		do{
			scanf("%s",&z);
			if((z=='c') ||(z=='C')) {
				print_();
				break;
			}
			if((z=='k')||(z=='K')) break;
		}while((z=='C')||(z=='c')||(z=='k')||(z=='K'));	
	}
}
 
 
int main()
{
  FILE *fr;
  int i,j = 0;
 
  if ((fr = fopen("sudoku.txt", "r")) == NULL) {
    printf("\nFile sudoku.txt cannot be found.");
    return 0;
  }
  fr = fopen("sudoku.txt","r");
  for (i = 1; i <= 9; i++) {
    for (j = 1; j <= 9; j++) 
      fscanf(fr, "%d ", &a[i][j]);
  }
  fclose(fr);
 
  do {
  	count_blank();
  	printf("(%d,%d}:%d\n",d[1].x,d[1].y,d[1].z);
  	find(d[1].x,d[1].y);
  	if(t-1==0) break;
  	if (lose) break;
  }while((t-1<0)||!lose);
  print_();
  return 0;
}
